package com.rayboo.example.algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 选择排序
 *
 * @author ray
 * @since 2019/08/01
 *
 * <p>(a)原理：每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。
 * 也就是：每一趟在n-i+1(i=1，2，…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。
 * 基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。（这里只介绍常用的简单选择排序）
 *
 * <p>(b)基本思想：给定数组：int[] arr={里面n个数据}；
 * 第1趟排序，在待排序数据arr[1]~arr[n]中选出最小的数据，将它与arr[1]交换；
 * 第2趟，在待排序数据arr[2]~arr[n]中选出最小的数据，将它与r[2]交换；
 * 以此类推，第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与r[i]交换，直到全部排序完成。
 *
 * <p>https://www.runoob.com/w3cnote/selection-sort.html
 */
public class SelectionSort {

    private ArrayList<Integer> arr;

    private SelectionSort(ArrayList<Integer> arr) {
        this.arr = arr;
    }

    public ArrayList<Integer> getArrayList() {
        return arr;
    }

    /**
     * 递归选择排序
     *
     * @param list 要排序的集合
     */
    public void sort(List<Integer> list) {

        int minimum = 0;
        if (list.size() <= 0) return;

        for (int j = 1; j < list.size(); j++) {

            if (list.get(j) < list.get(0)) {
                minimum = j;
                int temp = list.get(0);
                list.set(0, list.get(minimum));
                list.set(minimum, temp);
            }

        }

        sort(list.subList(1, list.size()));
    }

    /**
     * 选择排序
     *
     * @param arr 数组
     */
    public static void selectionSort(int[] arr) {
        int min, temp;
        // 做第i趟排序
        for (int i = 0; i < arr.length - 1; i++) {
            min = i;
            // 选最小的记录
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    //记下目前找到的最小值所在的位置
                    min = j;
                }
            }
            //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
            if (i != min) {
                //交换a[i]和a[k]
                temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }

    /**
     * 选择排序（倒序）
     *
     * @param arr 数组
     */
    public static void selectionSortDesc(int[] arr) {
        int max, temp;
        for (int i = 0; i < arr.length; i++) {
            // 初始化未排序序列中最小数据数组下标
            max = i;
            for (int j = i + 1; j < arr.length; j++) {
                // 在未排序元素中继续寻找最小元素，并保存其下标
                if (arr[j] > arr[max]) {
                    max = j;
                }
            }
            // 将未排序列中最小元素放到已排序列末尾
            if (max != i) {
                temp = arr[max];
                arr[max] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(20, 40, 10, 30, 50, 5));
        System.out.println("排序前：");
        System.out.println(Arrays.toString(list.toArray()));

        System.out.println("排序后：");
        SelectionSort selectionSort = new SelectionSort(list);
        selectionSort.sort(selectionSort.getArrayList());
        System.out.println(selectionSort.getArrayList());

        System.out.println("=================================");

        int[] arr = {1, 3, 2, 45, 65, 33, 12};
        System.out.println("排序前：\n" + Arrays.toString(arr));

        selectionSort(arr);
        System.out.println("排序后：\n" + Arrays.toString(arr));

        selectionSortDesc(arr);
        System.out.println("排序后(DESC)：\n" + Arrays.toString(arr));


    }
}
